
from chernc.treediff.gumtree.matchers.mapping_store import MappingStore
from chernc.treediff.gumtree.matchers.matcher import Matcher
from chernc.treediff.gumtree.tree.tree import TreeLike
from chernc.treediff.gumtree.tree.tree_utils import TreeUtils


class LcsMatcher(Matcher):
    def match(self, src: TreeLike, dst: TreeLike, mappings: MappingStore) -> MappingStore:
        # Get the pre-order traversal of the source and destination trees
        src_seq = TreeUtils.pre_order(src)
        dst_seq = TreeUtils.pre_order(dst)

        # Compute the longest common subsequence (LCS) with type and label
        lcs = SequenceAlgorithms.longest_common_subsequence_with_type_and_label(src_seq, dst_seq)

        # Add mappings based on the LCS
        for x in lcs:
            t1 = src_seq[x[0]]
            t2 = dst_seq[x[1]]
            mappings.add_mapping(t1, t2)

        return mappings
